package datastructure.sort;

import java.util.Arrays;

/**
 * 希尔排序
 *
 * @author jack.wu
 * @version 1.0
 * @date 2020-03-25
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] array = new int[]{5, 1, 9, -1, 4, 10};
        long startTime = System.currentTimeMillis();
//        shellSort(array);
        shellSort2(array);
        long endTime = System.currentTimeMillis();
        System.out.println(Arrays.toString(array));
        System.out.println("耗时：" + (endTime - startTime));
    }

    /**
     * 希尔排序
     * 交换法
     *
     * @param array
     */
    private static void shellSort(int[] array) {
        int temp = 0;
        int count = 0;
        for (int step = array.length / 2; step > 0; step /= 2) {
            for (int i = step; i < array.length; i++) {
                for (int j = i - step; j >= 0; j -= step) {
                    if (array[j] > array[j + step]) {
                        temp = array[j];
                        array[j] = array[j + step];
                        array[j + step] = temp;
                    }
                }
            }
            System.out.println("希尔排序第" + ++count + "次 ：" + Arrays.toString(array));
        }
    }

    /**
     * 希尔排序
     * 移动法
     * 和插入法类似
     * @param array
     */
    private static void shellSort2(int[] array) {
        for (int step = array.length / 2; step > 0; step /= 2) {
            for (int i = step; i < array.length; i++) {
                int insertIndex = i;
                int insertVal = array[insertIndex];
                if (array[insertIndex] < array[insertIndex - step]) {
                    while (insertIndex - step >=0 && insertVal < array[insertIndex - step]){
                        // 移动
                        array[insertIndex] = array[insertIndex - step];
                        insertIndex -= step;
                    }
                    array[insertIndex] = insertVal;
                }
            }
        }
    }


}
